The task of labeling or classifying unknown data to a set of known data arises in many fields, including computer vision, bioinformatics, computational linguistics, and speech recognition. For example, given an image comprising individual pixels, each pixel may be labeled as either foreground or background. Alternatively, each pixel may be labeled as being a member of the set of pixels belonging to one object or another object in the image. Other labeling applications are contemplated.
Probabilistic graphical models have emerged as a tool for building computer vision models. Conditional Random Fields (CRFs) represent a powerful class of models for labeling problems. In one view, CRFs provide a probabilistic framework for labeling and segmenting sequential data based on a model that defines a conditional probability p(y|x) over labels y given a particular observation x. For example, such conditional models may be used to label an unknown pixel x by selecting the label y that maximizes the conditional probability p(y|x). However, existing models for implementing accurate CRFs have generally proven intractable.